1. Field of the Invention
The present invention relates generally to visualizing data points, and in particular, to a method, apparatus, and article of manufacture for quickly visualizing large point cloud data at a high resolution.
2. Description of the Related Art
Point clouds are often created by three-dimensional (3D) scanners that measure a large number of points (e.g., from thousands to many billions of points [3D coordinates]) on the surface of an object, and output a point cloud as a data file. The point cloud represents the visible surface of the object that has been scanned or digitized. To quickly examine and visualize the dataset, some form of indexing or organization of the dataset is required. Prior art solutions fail to provide a quick and easy mechanism to both pre-process and view points in a dataset. Such problems may be better understood with a detailed description of prior art point cloud pre-processing and viewing methodologies.
Point clouds may be used for many purposes including to create computer-aided design (CAD) models for parts, animation, rendering, and/or large customization applications. However, due to the size and number of points in a point cloud, point cloud datasets are rarely directly used in 3D applications. Instead, the point cloud dataset may be converted to a triangle mesh model, a NURBS (non-uniform rational B-spline) surface model, or a CAD model. However, each of conversions involves significant pre-processing and does not provide an efficient mechanism for visualizing point cloud data in real time.
As part of the visualization processing, prior art solutions often involve creating a spatial index, often by creating a hierarchical representation of the point data. For example, a grid may be used to perform a tessellation of the point cloud data set that divides the dataset into a series of cells. Each cell can then be assigned a unique identifier and used for spatial indexing. However, such spatial index/hierarchical representation creation has numerous drawbacks. For example, pre-processing time can be extensive, often extending several hours or more. In addition, point extraction (e.g., the selection and viewing of a subset of the cloud point data) can be slow due to the amount of seeks (the process of moving a read head to a different location on a disk) required to gather the points from disk. In this regard, point data is often stored at multiple resolutions, resulting in large index and data files, significantly impacting the speed to extract and view a subset of the datapoints, and also significantly impacting the memory required to store the extra resolutions).
Accordingly, what is needed is the capability to rapidly index a point cloud data set while providing for rapid point extraction and viewing (e.g., in real time).